OpenAGH e-podręczniki | Metoda eliminacji Gaussa

Przedstawiony poniżej sposób rozwiązywania układów równań liniowych jest pewnym uproszczeniem algorytmu zwanego metodą eliminacji Gaussa. Metoda ta, niezwykle efektywna pod względem numerycznym (nie istnieje algorytm rozwiązywania układów równań wymagający istotnie mniejszej liczby działań niż metoda eliminacji Gaussa), polega na sprowadzeniu macierzy uzupełnionej, odpowiadającej rozwiązywanemu układowi równań, do uogólnionej postaci trójkątnej (nazywanej również postacią schodkową). Aby osiągnąć ten efekt, na macierzy uzupełnionej wykonujemy dwa rodzaje operacji:

dodajemy do wybranego wiersza sumy pozostałych wierszy pomnożonych przez odpowiednio dobrane stałe;
zamieniamy kolejność wierszy.

Operacje te nie wpływają na rozwiązania układu, nie zmieniają też rzędu macierzy. Do uzyskanej po zastosowaniu tych operacji macierzy stosujemy twierdzenie Kroneckera-Capelliego.

Warto przypomnieć w tym miejscu, że pierwsza z wymienionych powyżej operacji nie zmienia wartości wyznacznika macierzy, druga może zmienić jedynie jego znak. W efekcie, metoda eliminacji Gaussa może być z powodzeniem stosowana zarówno do obliczania rzędu i wyznacznika macierzy, jak i do wyznaczania macierzy odwrotnej.

Rozwiązywanie układów równań liniowych metodą eliminacji Gaussa

Ideę metody eliminacji Gaussa wyjaśnimy na kilku przykładach.

Przykład 1: Rozwiązywanie układu oznaczonego metodą eliminacji Gaussa

Celem naszym jest rozwiązanie układu równań

(1)

\( \left\{ \begin{array}{r} 2x+y+z+w=0\\ -x-2y-z+w=1\\ x+y-2z-3w=2\\ 4x-2y+4w=2 \end{array} \right. \)

przy użyciu metody eliminacji Gaussa.
Macierz uzupełniona \( U \) rozważanego układu ma postać

\( U=\left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0\\ -1 & -2 & -1 & 1 & 1\\ 1 & 1 & -2 & -3 & 2\\ 4 & -2 & 0 & 4 & 2 \end{array}\right) . \)

W pierwszym kroku metody eliminacji Gaussa wykorzystujemy pierwszy wiersz, nazywany wierszem głównym dla pierwszego kroku. Liczbę \( 2 \), pierwszy niezerowy element wiersza głównego, nazywamy elementem głównym dla pierwszego kroku. Celem naszym jest wyzerowanie wszystkich elementów stojących pod liczbą \( 2 \)(tj. pod elementem głównym dla pierwszego kroku) i utworzenie w ten sposób pierwszego schodka macierzy. Aby to osiągnąć, postępujemy w sposób następujący: do drugiego wiersza dodajemy pierwszy pomnożony przez \( (\frac{1}{2} \) do trzeciego pomnożony przez \( (-\frac{1}{2} \) do czwartego pomnożony przez \( -2 \). Otrzymujemy

\( \begin{array}{lll} \left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0 \\ -1 & -2 & -1 & 1 & 1 \\ 1 & 1 & -2 & -3 & 2 \\ 4 & -2 & 0 & 4 & 2 \end{array} \right) & \rightarrow\left\vert \begin{array}{l} w_{1} \rightarrow w_{1}\\ w_{2} \rightarrow w_{2}+\frac{1}{2}w_{1}\\ w_{3}\rightarrow w_{3}-\frac{1}{2}w_{1}\\ w_{4}\rightarrow w_{4}-2w_{1} \end{array}\right. \rightarrow\\ & \rightarrow\left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0 \\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2} & 1\\ 0 & \frac{1}{2} & -\frac{5}{2} & -\frac{7}{2} & 2\\ 0 & -4 & -2 & 2 & 2 \end{array} \right) . \end{array} \)

W kolejnym kroku, wierszem głównym jest wiersz drugi nazywany wierszem głównym dla drugiego kroku; elementem głównym dla drugiego kroku jest \( -\frac{3}{2} \). Celem naszym jest wyzerowanie wszystkich współczynników stojących pod liczbą \( -\frac{3}{2} \)(tj. pod elementem głównym dla drugiego kroku) i utworzenie w ten sposób drugiego schodka. Postępujemy analogicznie jak w kroku pierwszym: do wiersza trzeciego dodajemy wiersz drugi pomnożony przez \( \frac{1}{3} \) do wiersza czwartego pomnożony przez \( -\frac{8}{3} \). Otrzymujemy:

\( \begin{array}{lll} \left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0\\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2} & 1\\ 0 & \frac{1}{2} & -\frac{5}{2} & -\frac{7}{2}& 2\\ 0 & -4 & -2 & 2 & 2 \end{array} \right) &\rightarrow \left\vert \begin{array}{l} w_{1}\rightarrow w_{1}\\ w_{2}\rightarrow w_{2}\\ w_{3}\rightarrow w_{3}+\frac{1}{3}w_{2}\\ w_{4}\rightarrow w_{4}-\frac{8}{3}w_{2} \end{array} \right. \rightarrow \\ &\rightarrow \left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0 \\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2} & 1 \\ 0 & 0 & -\frac{8}{3} & -3 & \frac{7}{3}\\ 0 & 0 & -\frac{2}{3} & -2 & -\frac{2}{3} \end{array} \right) .\end{array} \)

W ostatnim, trzecim kroku wierszem głównym jest wiersz trzeci - wiersz główny dla kroku trzeciego; elementem głównym jest \( -\frac{8}{3} \). Mnożąc trzeci wiersz przez \( -\frac{1}{4} \) i dodając do wiersza czwartego otrzymujemy:

(2)

\( \begin{array}{lll} \left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0 \\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2} & 1\\ 0 & 0 & -\frac{8}{3} & -3 & \frac{7}{3}\\ 0 & 0 & -\frac{2}{3} & -2 & -\frac{2}{3} \end{array} \right) & \rightarrow \left\vert \begin{array}{l} w_{1}\rightarrow w_{1}\\ w_{2}\rightarrow w_{2}\\ w_{3}\rightarrow w_{3}\\ w_{4}\rightarrow w_{4}-\frac{1}{4}w_{3} \end{array} \right. \rightarrow \\ &\rightarrow \left( \begin{array}{cccc|c} 2 & 1 & 1 & 1 & 0 \\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2} & 1\\ 0 & 0 & -\frac{8}{3} & -3 & \frac{7}{3}\\ 0 & 0 & 0 & -\frac{5}{4} & -\frac{5}{4} \end{array} \right) .\end{array} \)

Uzyskana w ten sposób macierz schodkowa jest macierzą uzupełnioną układu równań posiadającego te same rozwiązania, co wyjściowy układ:

\( \left\{ \begin{array}{r} 2x+y+z+w=0\\ -\frac{3}{2}y-\frac{1}{2}z+\frac{3}{2}w=1\\ -\frac{8}{3}z-3w=\frac{7}{3}\\ -\frac{5}{4}w=-\frac{5}{4} \end{array} \right. . \)

Z postaci macierzy widać również, że układ ten posiada dokładnie jedno rozwiązanie (macierz układu, jako macierz trójkątna górna o niezerowych elementach na głównej przekątnej, jest macierzą nieosobliwą) . Wyznaczymy je rozwiązując otrzymany układ równań w kolejności od ostatniego równania do pierwszego. Uzyskujemy kolejno: \( w=1,z=-2,y=1,x=0. \)
Warto zanotować, że operacje jakie wykonywaliśmy na macierzy wyjściowego układu równań ( 1 ), aby sprowadzić ją do postaci trójkątnej ( 2 ) nie zmieniły jej wyznacznika. Ponieważ wyznacznik macierzy trójkątnej równy jest iloczynowi wyrazów z głównej przekątnej, mamy

\( \left\vert \begin{array}{cccc} 2 & 1 & 1 & 1\\ -1 & -2 & -1 & 1\\ 1 & 1 & -2 & -3\\ 4 & -2 & 0 & 4 \end{array} \right\vert =\left\vert \begin{array}{cccc} 2 & 1 & 1 & 1\\ 0 & -\frac{3}{2} & -\frac{1}{2} & \frac{3}{2}\\ 0 & 0 & -\frac{8}{3} & -3\\ 0 & 0 & 0 & -\frac{5}{4} \end{array} \right\vert =2\cdot\left( -\frac{3}{2}\right) \cdot\left( -\frac{8}{3}\right) \cdot\left( -\frac{5}{4}\right) =-10\text{.} \)

Przykład 2: Rozwiązywanie układu nieoznaczonego metodą eliminacji Gaussa

Rozważmy układ równań

(3)

\( \left\{\begin {array}{r}2x+3y-4z=6\\-4x+2z=0\\2y-2z=4\end{array}\right. \)

Macierz uzupełniona tego układu ma postać

(4)

\( U=\left( \begin{array}{ccc|c}2 & 3 & -4 & 6\\-4 & 0 & 2 & 0\\0 & 2 & -2 & 4\end{array}\right) \)

W pierwszym kroku metody eliminacji Gaussa do wiersza drugiego dodajemy wiersz pierwszy pomnożony przez \( 2 \); wiersz trzeci natomiast przepisujemy bez zmian:

(5)

\( \left(\begin{array}{ccc|c}2 & 3 & -4 & 6\\-4 & 0 & 2 & 0\\0 & 2 & -2 & 4\end{array}\right) \rightarrow\left\vert\begin{array}{l}w_{1}\rightarrow w_{1}\\w_{2}\rightarrow w_{2}+2w_{1}\\w_{3}\rightarrow w_{3}\end{array}\right. \rightarrow\left(\begin{array}{ccc|c}2 & 3 & -4 & 6\\0 & 6 & -6 & 12\\0 & 2 & -2 & 4\end{array}\right) \)

W kroku drugim, do wiersza trzeciego dodajemy wiersz drugi pomnożony przez \( -\frac{1}{3}: \)

\( \left( \begin{array}{ccc|c} 2 & 3 & -4 & 6\\ 0 & 6 & -6 & 12 \\ 0 & 2 & -2 & 4 \end{array} \right) \rightarrow\left\vert \begin{array}{l} w_{1}\rightarrow w_{1}\\ w_{2}\rightarrow w_{2}\\ w_{3}\rightarrow w_{3}-\frac{1}{3}w_{2} \end{array} \right. \rightarrow\left( \begin{array}{ccc|c} 2 & 3 & -4 & 6\\ 0 & 6 & -6 & 12\\ 0 & 0 & 0 & 0 \end{array} \right) . \)

Wykonywane operacje nie zmieniły rzędu macierzy, zatem

(6)

\( \operatorname*{rz}(A)=\operatorname*{rz}(U)=\operatorname*{rz}\left( \begin{array}{ccc|c}2 & 3 & -4 & 6\\-4 & 0 & 2 & 0\\0 & 2 & -2 & 4\end{array}\right)=\operatorname*{rz}\left( \begin{array}{ccc|c} 2 & 3 & -4 & 6\\ 0 & 6 & -6 & 12\\ 0 & 0 & 0 & 0 \end{array} \right)=\operatorname*{rz}\left(\begin{array}{cc} 2 & 3\\ 0 & 6\end{array} \right)=2. \)

Na podstawie twierdzenia Kroneckera-Capelliego, rozważany układ równań posiada nieskończenie wiele rozwiązań zależnych od \( n-r=3-\operatorname*{rz}(A)=3-2=1 \) parametru. Jest on równoważny układowi

(7)

\( \left\{\begin{array}{l}2x+3y-4z=6\\6y-6z=12\end{array}\right. , \)

którego rozwiązania, równe rozwiązaniom wyjściowego układu, mają postać \( x=t,y=2+2t,z=2t, \) gdzie \( t\in\mathbb{R} \) jest dowolnym parametrem.

Przykład 3: Rozwiązywanie układu sprzecznego metodą eliminacji Gaussa

Rozważmy układ równań

(8)

\( \left\{\begin{array}{r}5x-2y-z=1\\-2x+2y-2z=2\\-x-2y+5z=1\end{array}\right. , \)

którego macierz uzupełniona \( U \) ma postać

(9)

\( U=\left(\begin{array}{ccc|c}5 & -2 & -1 & 1\\-2 & 2 & -2 & 2\\-1 & -2 & 5 & 1\end{array}\right) . \)

W pierwszym kroku metody eliminacji Gaussa do wiersza drugiego dodajemy wiersz pierwszy pomnożony przez \( \frac{2}{5} \); do wiersza trzeciego pomnożony przez \( \frac{1}{5} \):

\( \left( \begin{array}{ccc|c} 5 & -2 & -1 & 1\\ -2 & 2 & -2 & 2\\ -1 & -2 & 5 & 1 \end{array} \right) \rightarrow\left\vert \begin{array}{l} w_{1}\rightarrow w_{1}\\ w_{2}\rightarrow w_{2}+\frac{2}{5}w_{1}\\ w_{3}\rightarrow w_{3}+\frac{1}{5}w_{1} \end{array} \right. \rightarrow\left( \begin{array}{ccc|c} 5 & -2 & -1 & 1 \\ 0 & \frac{6}{5} & -\frac{12}{5} & \frac{12}{5}\\ 0 & -\frac{12}{5} & \frac{24}{5} & \frac{6}{5} \end{array} \right) . \)

W drugim kroku do wiersza trzeciego dodajemy wiersz drugi pomnożony przez \( 2 \):

\( \left( \begin{array}{ccc|c} 5 & -2 & -1 & 1\\ 0 & \frac{6}{5} & -\frac{12}{5} & \frac{12}{5}\\ 0 & -\frac{12}{5} & \frac{24}{5} & \frac{6}{5} \end{array} \right) \rightarrow\left\vert \begin{array}{l} w_{1}\rightarrow w_{1}\\ w_{2}\rightarrow w_{2}\\ w_{3}\rightarrow w_{3}+2w_{2} \end{array} \right. \rightarrow\left( \begin{array}{ccc|c} 5 & -2 & -1 & 1\\ 0 & \frac{6}{5} & -\frac{12}{5} & \frac{12}{5}\\ 0 & 0 & 0 & 6 \end{array} \right) . \)

Wykonane operacje nie zminiły rzędu macierzy, zatem

(10)

\( \operatorname*{rz}(A)=\operatorname*{rz}\left(\begin{array}{ccc}5 & -2 & -1\\-2 & 2 & -2\\-1 & -2 & 5\end{array}\right)=\operatorname*{rz}\left( \begin{array}{ccc} 5 & -2 & -1 \\ 0 & \frac{6}{5} & -\frac{12}{5}\\ 0 & 0 & 0\end{array} \right)=\operatorname*{rz}\left( \begin{array}{ccc} 5 & -2\\ 0 & \frac{6}{5}\end{array} \right)=2 \)

oraz

(11)

\( \operatorname*{rz}(U)=\operatorname*{rz}\left(\begin{array}{ccc|c}5 & -2 & -1 & 1\\-2 & 2 & -2 & 2\\-1 & -2 & 5 & 1\end{array}\right)=\left( \begin{array}{ccc|c} 5 & -2 & -1 & 1\\ 0 & \frac{6}{5} & -\frac{12}{5} & \frac{12}{5}\\ 0 & 0 & 0 & 6 \end{array} \right)=\left( \begin{array}{cc|c} 5 & -2 & 1\\ 0 & \frac{6}{5} & \frac{12}{5}\\ 0 & 0 & 6 \end{array} \right)=3. \)

Na podstawie twierdzenia Kroneckera-Capelliego stwierdzamy, że rozważany układ równań nie posiada rozwiązań. Warto zauważyć, że sprzeczność tego układu można odczytać nie tylko z przeprowadzonego rachunku rzędów, lecz również z postaci macierzy schodkowej - wiersz trzeci tej macierzy odpowiada równaniu sprzecznemu \( 0x+0y+0z=6 \).

Wyznaczanie macierzy odwrotnej z wykorzystaniem metody eliminacji Gaussa

Niech \( A\in\mathbb{R}^{n\times n} \) będzie zadaną macierzą nieosobliwą (warunek ten gwarantuje istnienie macierzy \( A^{-1} \) ) oraz niech \( X_i \) oznacza \( i \)-tą kolumnę poszukiwanej macierzy \( A^{-1} \), tj. \( A^{-1}=(X_1,\ldots, X_n) \). Łatwo sprawdzić, że przy przyjętych oznaczeniach

(12)

\( A\cdot A^{-1}=A\cdot (X_1,\ldots, X_n) = (A\cdot X_1,\ldots, A\cdot X_n). \)

Dzięki tej prostej obserwacji równanie \( A\cdot X=I \), którego jedynym rozwiązaniem jest \( X=A^{-1} \), możemy zapisać w postaci \( n \) układów równań liniowych:

(13)

\( \begin{array}{l}A\cdot X_1 = (1,0,0,\ldots ,0)^T,\\A\cdot X_2 = (0,1,0,\ldots ,0)^T,\\\hspace{0.5cm}\vdots\\A\cdot X_n = (0,0,\ldots,0,1)^T,\end{array} \)

których rozwiązaniami są kolejne kolumny macierzy \( A^{-1} \). Do rozwiązania każdego z tych układów równań możemy zastosować algorytm eliminacji Gaussa.

Zaproponowaną metodę wyznaczania macierzy odwrotnej, która w literaturze funkcjonuje również jako metoda Gaussa-Jordana, przedstawimy na prostym przykładzie.

Przykład 4: Wyznaczanie macierzy odwrotnej z wykorzystaniem metody eliminacji Gaussa

Rozważmy macierz

(14)

\( A=\left(\begin{array}{ccc}1 & 1 & 0\\-2 & 1 & 2\\1 & 2 & -1\end{array}\right). \)

Jak łatwo sprawdzić \( \det(A)=-5\neq 0 \), zatem macierz \( A \) posiada macierz odwrotną. Wyznaczymy ją wykorzystując metodę eliminacji Gaussa. Operacje wykonywane na macierzy \( A \) przeprowadzamy jednocześnie na macierzy jednostkowej, którą dla wygody zapiszemy z prawej strony. Zabieg ten umożliwi rozwiązanie za jednym razem trzech układów równań

(15)

\( \left(\begin{array}{ccc}1 & 1 & 0\\-2 & 1 & 2\\1 & 2 & -1\end{array}\right) X_1 = \left(\begin{array}{c}1\\ 0\\ 0 \end{array}\right),\hspace{0.5cm}\left(\begin{array}{ccc}1 & 1 & 0\\-2 & 1 & 2\\1 & 2 & -1\end{array}\right) X_2 = \left(\begin{array}{c}0\\ 1\\ 0 \end{array}\right),\hspace{0.5cm}\left(\begin{array}{ccc}1 & 1 & 0\\-2 & 1 & 2\\1 & 2 & -1\end{array}\right) X_3 = \left(\begin{array}{c}0\\ 0\\1 \end{array}\right), \)

których rozwiązaniami są kolejne kolumny macierzy \( A^{-1} \).
W pierwszym kroku sprowadzimy macierz \( A \) do postaci trójkątnej. Mamy zatem

(16)

\( \left(\begin{array}{ccc|ccc}1 & 1 & 0 & 1 & 0 & 0\\-2 & 1 & 2 & 0 & 1 & 0\\1 & 2 & -1 & 0 & 0 & 1\end{array}\right) . \)

Dodając do wiersza drugiego wiersz pierwszy pomnożony przez \( 2 \); do trzeciego pomnożony przez \( -1 \) otrzymujemy

(17)

\( \left(\begin{array}{ccc|ccc}1 & 1 & 0 & 1 & 0 & 0\\0 & 3 & 2 & 2 & 1 & 0\\0 & 1 & -1 & -1 & 0 & 1\end{array}\right). \)

Dodając do wiersza trzeciego drugi pomnożony przez \( -\frac{1}{3} \) otrzymujemy

\( \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 3 & 2 & 2 & 1 & 0\\ 0 & 0 & -\frac{5}{3} & -\frac{5}{3} & -\frac{1}{3} & 1 \end{array} \right) . \)

Ponieważ wykonane operacje nie zmieniły wyznacznika macierzy, zatem widzimy, że faktycznie \( \det A=-5 \). Uzyskana macierz jest już macierzą trójkątną, możemy więc przejść do kroku drugiego. Polega on na sprowadzeniu macierzy trójkątnej do postaci diagonalnej. Aby to osiągnąć stosujemy metodę eliminacji idąc w kolejności odwrotnej - od wiersza trzeciego do pierwszego. Dodając do wiersza drugiego trzeci pomnożony przez \( \frac{6}{5} \), otrzymujemy

\( \left( \begin{array}{ccc|ccc} 1 & 1 & 0 & 1 & 0 & 0\\ 0 & 3 & 0 & 0 & \frac{3}{5} & \frac{6}{5}\\ 0 & 0 & -\frac{5}{3} & -\frac{5}{3} & -\frac{1}{3} & 1 \end{array} \right) . \)

Dodając do wiersza pierwszego drugi pomnożony przez \( -\frac{1}{3} \) otrzymujemy

\( \left( \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & -\frac{1}{5} & -\frac{2}{5}\\ 0 & 3 & 0 & 0 & \frac{3}{5} & \frac{6}{5}\\ 0 & 0 & -\frac{5}{3} & -\frac{5}{3} & -\frac{1}{3} & 1\end{array} \right) . \)

Ostatnim etapem jest przekształcenie uzyskanej macierzy diagonalnej do macierzy jednostkowej. W tym celu wystarczy wiersz drugi pomnożyć przez \( \frac{1}{3} \), trzeci przez \( -\frac{3}{5} \) otrzymując:

\( \left( \begin{array}{ccc|ccc} 1 & 0 & 0 & 1 & -\frac{1}{5} & -\frac{2}{5}\\ 0 & 1 & 0 & 0 & \frac{1}{5} & \frac{2}{5}\\ 0 & 0 & 1 & 1 & \frac{1}{5} & -\frac{3}{5}\end{array} \right) . \)

W wyniku zastosowanych operacji uzyskaliśmy układ równań o macierzy jednostkowej. Kolejne kolumny macierzy stojącej z prawej strony tej macierzy są więc poszukiwanymi rozwiązaniami \( X_1, X_2, X_3 \) tworzącymi macierz \( A^{-1} \):

\( A^{-1}=\frac{1}{5} \left( \begin{array}{ccc} 5 & -1 & -2\\ 0 & 1 & 2\\ 5 & 1 & -3 \end{array} \right) . \)

Temat:
Opis:
Typ:

Email:

Matematyka

Metoda eliminacji Gaussa